package September20;

public class LongestRepeatingSubstring {
    public static void main(String[] args) {
        String str1 = "abcfabc";
        String str2 = "afkafk";

        System.out.println("最长的重复子串是: " + findLongestRepeatingSubstring(str1));
        System.out.println("最长的重复子串是: " + findLongestRepeatingSubstring(str2));
    }

    public static String findLongestRepeatingSubstring(String str) {
        int n = str.length();
        int maxLen = 0;
        String longestSubstring = "";

        for (int len = 1; len <= n / 2; len++) { // 只需要检查到一半，因为重复子串不会超过一半
            for (int i = 0; i <= n - len; i++) {
                String substr = str.substring(i, i + len);
                if (isRepeating(str, substr) && substr.length() > maxLen) {
                    maxLen = substr.length();
                    longestSubstring = substr;
                }
            }
        }

        return longestSubstring;
    }

    private static boolean isRepeating(String str, String substr) {
        int index = str.indexOf(substr);
        if (index == -1) {
            return false;
        }
        int repeatCount = 1;

        while (index + substr.length() <= str.length()) {
            index = str.indexOf(substr, index + substr.length());
            if (index == -1) {
                break;
            }
            repeatCount++;
        }

        return repeatCount > 1;
    }
}
